GATE CSE 2021 SET-2
Q1.
Consider the following ANSI C code segment: z=x + 3 + y-> f1 + y-> f2; for (i = 0; i < 200; i = i + 2) { if (z > i) { p = p + x + 3; q = q + y-> f1; } else { p = p + y-> f2; q = q + x + 3; } }Assume that the variable y points to a struct (allocated on the heap) containing two fields f1 and f2, and the local variables x, y, z, p, q, and i are allotted registers. Common sub-expression elimination (CSE) optimization is applied on the code. The number of addition and the dereference operations (of the form y -> f1 or y -> f2) in the optimized code, respectively, are:203 and 2
203 and 2303 and 102
403 and 102
303 and 2
Q2.
Consider the following ANSI C program. #include < stdio.h > int main( ) { int arr[4][5]; int i, j; for (i=0; i < 4; i++) { for (j=0; j < 5; j++) { arr[i][j] = 10 * i + j; } } printf("%d", *(arr[1]+9)); return 0; } What is the output of the above program?14
24
20
30
Q3.
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?\Theta ( n)
\Theta ( \log _2 (n))
\Theta ( n^2)
\Theta (\sqrt{n})
Q4.
Consider a set-associative cache of size 2KB (1KB=2^{10} bytes) with cache block size of 64 bytes. Assume that the cache is byte-addressable and a 32 -bit address is used for accessing the cache. If the width of the tag field is 22 bits, the associativity of the cache is ______16
8
2
4
Q5.
Assume a two-level inclusive cache hierarchy, L1 and L2, where L2 is the larger of the two. Consider the following statements. S1: Read misses in a write through L1 cache do not result in writebacks of dirty lines to the L2 S2: Write allocate policy must be used in conjunction with write through caches and no-write allocate policy is used with writeback caches. Which of the following statements is correct?S1 is false and S2 is true
S1 is false and S2 is false
S1 is true and S2 is true
S1 is true and S2 is false
Q6.
Suppose that f: \mathbb{R} \rightarrow \mathbb{R} is a continuous function on the interval [-3,3] and a differentiable function in the interval (-3,3) such that for every x in the interval, f'(x) \leq 2. If f(-3) =7, then f(3) is at most __________19
32
11
54
Q7.
For two n-dimensional real vectors P and Q, the operation s(P,Q) is defined as follows: s(P,Q) = \displaystyle \sum_{i=1}^n (P[i] \cdot Q[i]) Let \mathcal{L} be a set of 10-dimensional non-zero real vectors such that for every pair of distinct vectors P,Q \in \mathcal{L}, s(P,Q)=0. What is the maximum cardinality possible for the set \mathcal{L}?9
100
11
10
Q8.
Consider a complete binary tree with 7 nodes. Let A denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let B denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root. The value of |A-B| is _____________2
4
1
3
Q9.
For a string w, we define w^R to be the reverse of w. For example, if w=01101 then w^R=10110. Which of the following languages is/are context-free?[MSQ]\{ wxw^Rx^R \mid w,x \in \{0,1\} ^* \}
\{ wxw^R \mid w,x \in \{0,1\} ^* \}
\{ wxx^Rw^R \mid w,x \in \{0,1\} ^* \}
\{ ww^Rxx^R \mid w,x \in \{0,1\} ^* \}
Q10.
Let L_1 be a regular language and L_2 be a context-free language. Which of the following languages is/are context-free?[MSQ]L_1 \cup (L_2 \cup \overline{L_2})
(L_1 \cap L_2) \cup (\overline{L_1} \cap L_2)
\overline{\overline{L_1} \cup \overline{L_2}}
L_1 \cap \overline{L_2}